/*
 * @lc app=leetcode id=68 lang=cpp
 *
 * [68] Text Justification
 */
class Solution {
public:

    int nextWord(vector<string>& words, int maxWidth, int st) {
        int i = st;
        int l = 0;
        int wlen = 0;

        while(i < words.size()) {
            int wl = words[i].size();
            int tmplen = l + wl;
            if (l > 0) {
                tmplen++;
            }
            if (tmplen <= maxWidth) {
                l = tmplen;
                wlen += wl;
            } else {
                break;
            }
            i++;
        }
        return i;
    }
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ret;

        int idx = 0;
        int wnum = words.size();
        while(idx < wnum) {

            int nextw = nextWord(words, maxWidth, idx);

            int wlen = 0;
            for (int i=idx; i<nextw; i++) {
                wlen += words[i].size();
            }

            int spaceLen = maxWidth - wlen;
            int wc = nextw-idx;
            if (wc == 1) {
                string line = words[idx];
                int wl = line.size();
                if (maxWidth > wl) {
                    line += string(maxWidth-wl, ' ');
                }
                ret.push_back(line);
            } else if (wc > 1) {
                int spaceNumber = wc-1;
                vector<int> space(spaceNumber, 0);
                for (int n=0; n<spaceNumber; n++) {
                    if (nextw == wnum) {
                        space[n] = 1;
                    } else {
                        if (n < spaceLen%spaceNumber) {
                            space[n] = spaceLen/spaceNumber + 1;
                        } else {
                            space[n] = spaceLen/spaceNumber;
                        }
                    }
                }

                string line;
                int tail = 0;
                for (int n=0; n<wc; n++) {
                    if (n > 0) {
                        line += string(space[n-1], ' ');
                    }
                    line += words[n+idx];
                    tail += words[n+idx].size();
                }

                if (nextw == wnum) {
                    tail += spaceNumber;
                    if (tail < maxWidth) {
                        line += string(maxWidth-tail, ' ');
                    }
                }
                ret.push_back(line);
            }
            
            idx = nextw;
        }
        return ret;
    }
};

